/*
 * kdtree.h
 *
 *  Created on: Apr 27, 2011
 *      Author: tqlong
 */

#ifndef KDTREE_H_
#define KDTREE_H_

#include "tree.h"

class BoundingBox
{
  vec m_min, m_max;
  int n_dim;
public:
  BoundingBox(int dim);

  void accumulate(const vec& v);
  void accumulate(const BoundingBox& b);

  const vec& min() const;
  const vec& max() const;

  double lowerBound(const vec& v) const;

  void print() const;
};

class KDTree : public TreeTemplate<KDTree>
{
protected:
  typedef TreeTemplate<KDTree>  __Base;
  //typedef __Base::dataset_type  dataset_type;

  BoundingBox m_box;
public:
  KDTree(const dataset_type& data);
  KDTree(KDTree* parent, int s, int e);

  const BoundingBox& box() const;
  BoundingBox& stats();
  const BoundingBox& stats() const;

  void split();
  void buildTreeAndStats()
  {
    buildTree();
    NodeStats<KDTree> v;
    visitRecursive(v, false);  // post-order visit
  }

  void findKNN(const vec& query, std::vector<int>& knnIdx, std::vector<double>& minBound);
  Tree* createChild(int s, int e) {
    return new KDTree(this, s, e);
  }

  // SEARCHER implements: bool ok(KDTree*, int idx), bool ok(BoundingBox), process(KDTree*, int idx)
  template<typename SEARCHER> double applyJob(SEARCHER& s);

protected:
  double find_max_variance(int& dim_max) const;
  double find_split_value(int dim) const;
  double min_dim(int dim) const;
  double max_dim(int dim) const;
  void split(int dim, double split_value);
};

template<typename SEARCHER>
double KDTree::applyJob(SEARCHER& s)
{
  if (!s.isFindAll() && s.isFound()) return 0;
  if (!s.ok(box())) return n();
  double pruned = 0;
  if (n_child() == 0) {
    for_all_node_data(i) if (s.ok(this, i)) {
      s.set_found(true);
      s.process(this, i);
      if (!s.isFindAll()) break;  // only need to find one instance
    }
  }
  else {
    for_all_node_child(i) {
      pruned += child(i)->applyJob(s);
      if (!s.isFindAll() && s.isFound()) break;
    }
  }
  return pruned;
}

#endif /* KDTREE_H_ */
